%File: formatting-instruction.tex
\documentclass[letterpaper]{article}
\usepackage{aaai}
\usepackage{times}
\usepackage{helvet}
\usepackage{courier}
\frenchspacing
\pdfinfo{
/Title (How does Iterative Deepening Search and A* compare in a Zeno-travel problem with varying numbers of cities)
/Subject (Solution to Assignment 1)
/Author (Wen Shen and Issak Gezehei)}
\setcounter{secnumdepth}{0}  
 \begin{document}
% The file aaai.sty is the style file for AAAI Press 
% proceedings, working notes, and technical reports.
%
\title{How Does Iterative Deepening Search and A* Compare in a Zeno-Travel Problem with Varying Numbers of Cities}
\author{Wen Shen and Issak Gezehei \\
Computing and Information Science Program\\
Masdar Institute of Science \& Technology\\
PO Box 54224, Abu Dhabi, UAE\\
}
\maketitle
\begin{abstract}
\begin{quote}
In this paper, we investigate the performances of Iterative Deepening Search (IDS) algorithm and A* Search(Astar) algorithm in a Zeno-Travel problem with varying numbers of cities. We implement the IDS algorithm and Astar algorithm based on the standard AIMA python code. We also build a random ZenoTravel generator to generate problems varying the numbers of cities. We then present a detailed analysis on these two algorithms based on the experiments.
\end{quote}
\end{abstract}

\section{Introduction}
In this paper, we investigate the performance of iterative deepening search(IDS) algorithm and A* search(Astar) algorithm in a Zeno-Travel problem with varying numbers of cities. The strips version of ZenoTravel domain from the 2002 International Planning Competition is selected as our domain. We implement the iterative deepening search algorithm and the A* algorithm based on the AIMA Python code. We also bulid a random ZenoTravel generator to generate ZenoTravel problem instances varying in the numbers of cities. We then test the performance of these two algorithms by running them on 100   ZenoTravel problems with numbers of cities varying from 1 to 50. We present the results and give a detailed analysis.

\section{Algorithms Design}
In this section, we present an analysis of the IDS and Astar algorithm.
\subsection{Iterative Deepening Search}
Iterative Deepening Search(IDS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state. On each iteration, IDS visits the nodes in the search tree as depth-first search, but the cumulative order in which nodes are first visited, assuming no pruning, is effectively breadth-first.

The space complexity of IDS is $O(bd)$, where $b$ is the branching factor and d is the depth of shallowest goal. The time complexity of IDS in well-balanced trees works out to be the same as Depth-first search:$O(b^{d})$.
\subsection{A* Search}
\section{The Comparision of the performance of IDS and Astar}
\section{ References}

\bigskip
\noindent Thank you for reading these instructions carefully. We look forward to receiving your electronic files!

\end{document}
